//2748.美丽下标对的数目
//https://leetcode.cn/problems/number-of-beautiful-pairs
class Solution {
    int gcd(int a,int b) {
        return b>0 ? gcd(b,a%b):a;
    }
public:
    int countBeautifulPairs(vector<int>& nums) {
        int n = nums.size();
        int hash[10] = {0}; //统计前i个数出现的最高位数
        int ret = 0;

        //枚举i
        for(int i = 0;i<n;++i)
        {
            int num = nums[i];
            //查找前i-1个数字中出现与i互质的数字的个数
            //j枚举的是低位1~9 下标下的数字表示前i-1个数中有多少个对应下标数字
            for(int j = 1;j<10;++j)
                if(gcd(num%10,j)==1) ret+=hash[j];

            //将i加入数组
            while(num>=10) num/=10;
            ++hash[num];
        }
        return ret;
    }
};

//暴力
// class Solution {
//     int gcd(int a,int b) {
//         return b>0 ? gcd(b,a%b):a;
//     }
// public:
//     int countBeautifulPairs(vector<int>& nums) {
//         int n = nums.size();
//         int ret = 0;

//         //枚举i
//         for(int i = 0;i<n;++i)
//         {
//             //枚举j
//             for(int j = i+1;j<n;++j)
//             {
//                 //取x的最高位 y的最低位
//                 int x = nums[i],y = nums[j]%10;
//                 while(x >= 10) x/=10;

//                 if(gcd(x,y) == 1) ++ret; //两数的最大公约数为1 则为质数
//             }
//         }
//         return ret;
//     }
// };